interface equalsFnType<T> {
  (a: T, b: T): boolean
}

class LinkedList<T> {
  private head: any
  private count: number
  private next: any
  private equalsFn: equalsFnType<T>

  constructor(equalsFn = defaultEquals) {
    // 初始化链表内部变量
    this.count = 0
    this.next = undefined
    this.equalsFn = equalsFn
    this.head = null
  }

  push(element: T) {
    const node = new Node(element)
    let current = null
    if (this.head == null) {
      this.head = node
    } else {
      current = this.head
      while (current.next) {
        current = current.next
      }
      current.next = node
    }
    this.count++
  }

  removeAt(index: number) {
    if (index >= 0 && index < this.count) {
      let current = this.head
      if (index == 0) {
        this.head = current.next
      } else {
        // 获取目标参数上一个结点
        let previous = this.getElementAt(index - 1)
        // 当前结点指向目标结点
        current = previous.next
        /**
         * 目标结点元素已找到
         * previous.next指向目标结点
         * current.next指向undefined
         * previous.next指向current.next即删除目标结点的元素
         */
        previous.next = current.next
      }
      this.count--
      // 返回当前删除的目标结点
      return current.element
    } else {
      return undefined
    }
  }
  getElementAt(index: number) {
    if (index >= 0 && index < this.count) {
      let current = this.head
      for (let i = 0; i < index && current !== undefined; i++) {
        current = current.next
      }
      return current
    }
    return undefined
  }
  insert(element: T, index: number) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element)
      if (index == 0) {
        node.next = this.head
        this.head = node
      } else {
        let provide = this.getElementAt(index - 1)
        node.next = provide.next
        provide.next = node
      }
      this.count++
      return true
    } else {
      return false
    }
  }
  indexOf(element: T) {
    let current = this.head
    for (let i = 0; i < this.count && current !== null; i++) {
      if (this.equalsFn(element, current.element)) {
        // 返回索引
        return i
      }
      current = current.next
    }
    return -1
  }
  remove(element: T) {
    // 获取element的索引,移除索引位置的元素
    this.removeAt(this.indexOf(element))
  }
  size(): number {
    return this.count
  }
  isEmpty(): boolean {
    return this.size() === 0
  }
  getHead() {
    return this.head
  }
  toString() {
    if (this.head == null) {
      return ''
    }
    let objString = `${this.head.element}`
    // 获取链表顶点的下一个结点
    let current = this.head.next
    // 遍历链表中的所有结点
    for (let i = 1; i < this.size() && current != null; i++) {
      // 将当前结点的元素拼接到最终要生成的字符串对象中
      objString = `${objString}, ${current.element}`
      // 当前结点指向链表的下一个元素
      current = current.next
    }
    return objString
  }
}

class Node<T> {
  element: T
  next: any

  constructor(element: T) {
    this.element = element
    this.next = undefined
  }
}

function defaultEquals(a: any, b: any) {
  return a === b
}

export { LinkedList, Node }
